package uestc.lj.advanced.dp;

import uestc.lj.leetcode.day1.LeetCode;
import uestc.lj.leetcode.day1.Solution;

/**
 * @Author:Crazlee
 * @Date:2021/12/10
 */
public class Code15_GasStations {
	public int canCompleteCircuit(int[] gas, int[] cost) {
		int n = gas.length;
		int i = 0;

		while (i < n) {
			int sumOfGas = 0, sumOfCost = 0;
			int cnt = 0;
			while (cnt < n) {
				int j = (i + cnt) % n;
				sumOfGas += gas[j];
				sumOfCost += cost[j];
				if (sumOfCost > sumOfGas) {
					break;
				}
				cnt++;
			}
			if (cnt == n) {
				return i;
			} else {
				i = i + cnt + 1;
			}
		}
		return -1;
	}


}
